/**318. 最大单词长度乘积
 * - 给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
 */
export function maxProduct(words: string[]): number {
    //双层for循环，然后判断这两个字母是否有重复的字母 （常规方法是转set去重后判断，但是仍然超时）
    //所以可以用位运算的知识 （在vue3源码的vnode的 shapeFlag 中也用了这种标记方式）
    //这题可以利用位运算的一个重要特性：每个比特位可以表示一个字母是否出现过。通过将每个字母映射到不同的比特位上，我们可以使用对应比特位的值来表示字母是否出现过，从而判断是否有重复字母。
    /*
        字母:    a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
        索引:    0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
        比特位:  0..01  0..10  ......................................................... 10...00
     */
    const bitVectors = new Array<number>(words.length).fill(0);
    //记录每个单词的字符二进制数据
    for (let i = 0; i < words.length; i++) {//遍历数组
        const word = words[i];
        let bitVector = 0;
        for (let j = 0; j < word.length; j++) { //遍历单词
            // 将对应索引位置的比特位设置为1
            bitVector |= 1 << (word.charCodeAt(j) - 97); // 将字符转换为对应的索引值 
        }
        bitVectors[i] = bitVector;
    }

    let res = 0;

    //双层for遍历，判断重复的方法使用位运算
    for (let i = 0; i < words.length; i++) {
        for (let j = i + 1; j < words.length; j++) {
            // 如果两个单词的比特向量与的结果为0，表示它们没有公共字母 （比如 001 和 011，最后一位重复了的话，得到的结果是1，而 001和010结果为0）
            if ((bitVectors[i] & bitVectors[j]) === 0) {
                const product = words[i].length * words[j].length;
                res = Math.max(res, product);
            }
        }
    }

    return res;
}